// 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。

//  

// 进阶：

// 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

//  

// 示例：

// 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
// 输出：7 -> 8 -> 0 -> 7

#include <stack>

using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/* 栈
时间复杂度：O(max(m, n))
空间复杂度：O(m+n)
*/
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1{};
        stack<int> s2{};
        while ( nullptr != l1 ) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while ( nullptr != l2 ) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int carry{0};
        ListNode* head{nullptr};
        while ( (!s1.empty()) || (!s2.empty()) || (carry != 0) ) {
            int a = ( s1.empty() ? 0 : s1.top() );
            int b = ( s2.empty() ? 0 : s2.top() );
            if ( !s1.empty() ) s1.pop();
            if ( !s2.empty() ) s2.pop();
            int sum = a + b + carry;
            carry = sum / 10;
            ListNode* cur = new ListNode(sum % 10);
            cur->next = head;
            head = cur;
        }
        return head;
    }
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1{};
        stack<int> s2{};
        ListNode* node1{l1};
        ListNode* node2{l2};
        while (node1) {
            s1.push(node1->val);
            node1 = node1->next;
        }
        while (node2) {
            s2.push(node2->val);
            node2 = node2->next;
        }
        int carry{0}; // 进位
        ListNode* res{nullptr}; // 现在res是最后一个节点的尾巴
        while (!s1.empty() || !s2.empty() || carry != 0) {
            int a = (s1.empty() ? 0 : s1.top());
            int b = (s2.empty() ? 0 : s2.top());
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int sum = a + b + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = res;
            res = node;
        }
        return res;
    }
};